package pers.vic.basics.datastructure.linked;

import java.util.Objects;

/**
 * @author Vic.xu
 * @description: 双端链表； 在单向列表的基础上多个对尾节点的引用，方便在尾部的新增节点
 * @date: 2020/10/19 0019 15:55
 */
public class DoublePointLinkedList implements LinkedInterface {

  //头节点
    private Node head;

    //尾节点
    private Node tail;

    //长度
    private int size;

    public DoublePointLinkedList() {
        head = null;
        tail = null;
        this.size = 0;
    }

    @Override
    public Object addHead(Object obj) {
        Node cur = new Node(obj);
        if (head == null) {
            head = cur;
            tail = cur;
        } else {
            cur.next = head;
            head = cur;
        }
        size++;
        return obj;
    }

    @Override
    public Object addTail(Object obj) {
        Node cur = new Node(obj);
        if (tail == null) {
            head = cur;
            tail = cur;
        } else {
            tail.next = cur;
            tail = cur;
        }
        size++;
        return obj;
    }

    @Override
    public Object deleteHead() {
        if (size == 0) {
            throw new IllegalStateException("链表为空");
        }
        Node next = head.next;
        if (next == null) {
            tail = null;
            head = null;
        } else {
            head = next;
        }

        return null;
    }

    @Override
    public Node find(Object obj) {
        Node cur = head;
        while (cur != null) {
            if (Objects.equals(cur.data, obj)) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

    @Override
    public boolean delete(Object obj) {
        if (size == 0) {
            return false;
        }

        Node cur = head;
        Node previous = null;

        boolean find = false;
        while (cur != null) {
            if(Objects.equals(cur.data, obj)) {
                find = true;
                break;
            }
            cur = cur.next;
            previous = cur;
        }
        if(!find) {
            return false;
        }
        Node next = cur.next;
        if(cur == head) {
           tail = null;
           head = null;
        }else {
            previous.next = next;
            // 如果是尾节点(非头结点) 则把上一个节点置为尾节点
            if(tail == cur) {
                tail = previous;
                tail.next = null;
            }

        }


        size--;
        return true;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void display() {
        if (size == 0) {
            System.out.println(" - ");
            return;
        }
        Node cur = head;
        while (cur != null) {
            System.out.print(cur.data + "->");
            cur = cur.next;
        }
        System.out.println();
    }

    @Override
    public int size() {
        return size;
    }
}
